#include <iostream>
#include <queue>
#include <stack>

namespace ys
{
    // 双队列实现栈
    template <class T>
    class stack
    {
    private:
        std::queue<T> _q_push;
        std::queue<T> _q_pop;

        void Move()
        {

            while (_q_push.size() != 1)
            {
                T val = _q_push.front();
                _q_push.pop();
                _q_pop.push(val);
            }
        }

    public:
        void push(const T &val)
        {
            _q_push.push(val);
        }
        void pop()
        {
            if (empty())
                return;

            Move();
            _q_push.pop();
            _q_push.swap(_q_pop);
        }

        bool empty()
        {
            return _q_push.size() == 0;
        }
        T top()
        {
            if (empty())
                return -1;

            Move();
            T ret = _q_push.front();
            _q_push.pop();
            _q_pop.push(ret);
            _q_push.swap(_q_pop);
            return ret;
        }
    };

    // 双栈实现队列
    template <class T>
    class queue
    {
    private:
        std::stack<T> _st_push;
        std::stack<T> _st_pop;

        void Move()
        {
            while (_st_push.size() != 0)
            {
                T val = _st_push.top();
                _st_push.pop();
                _st_pop.push(val);
            }
        }

    public:
        void push(const T &val)
        {
            _st_push.push(val);
        }
        void pop()
        {
            if (empty())
                return;

            if (_st_pop.size() == 0)
                Move();
            _st_pop.pop();
        }
        T front()
        {
            if (empty())
                return -1;

            if (_st_pop.size() == 0)
                Move();

            return _st_pop.top();
        }
        bool empty()
        {
            return (_st_pop.size() == 0) && (_st_push.size() == 0);
        }
    };
}

int main()
{
    ys::stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    st.push(5);

    while (!st.empty())
    {
        int val = st.top();
        std::cout << val << " ";
        st.pop();
    }
    std::cout << std::endl;

    ys::queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
    q.push(6);
    while (!q.empty())
    {
        int val = q.front();
        std::cout << val << " ";
        q.pop();
    }
    std::cout << std::endl;
    return 0;
}